package Sudoku;
class SudokuSolver {
    private final int[][] board;  // 存储数独的二维数组
    private int count;  // 存储解的数量

    // 构造函数，初始化数独和解的数量
    public SudokuSolver(int[][] board) {
        this.board = board;
        this.count = 0;
    }

    // 解数独的入口方法
    public void solve() {
        solveSudoku(0, 0);
    }

    // 递归解数独的方法
    private void solveSudoku(int row, int col) {
        // 如果已经遍历到数独的最后一个位置，增加解的数量并返回
        if (row == board.length - 1 && col == board[0].length) {
            count++;
            return;
        }

        // 如果当前列达到数独的最后一列，换行
        if (col == board[0].length) {
            row++;
            col = 0;
        }

        // 如果当前位置是空白的
        if (board[row][col] == 0) {
            // 尝试填充当前位置的数字
            for (int num = 1; num <= 9; num++) {
                if (isSafe(row, col, num)) { // 在当前位置填入数字是否合法
                    board[row][col] = num;   // 将数字填入当前位置
                    solveSudoku(row, col + 1);  // 递归调用，继续尝试下一个位置
                    board[row][col] = 0;  // 回溯，重置当前位置为0，尝试其他数字
                }
            }
        } else {
            // 如果当前位置已经有数字，直接进入下一列
            solveSudoku(row, col + 1);
        }
    }


    // 检查在当前位置填入数字是否合法
    private boolean isSafe(int row, int col, int num) {
        return !usedInRow(row, num) && !usedInColumn(col, num) && !usedInSubgrid(row - row % 3, col - col % 3, num);
    }

    // 检查在当前行是否已经使用了指定数字
    private boolean usedInRow(int row, int num) { //遍历实现
        for (int col = 0; col < board[0].length; col++) {
            if (board[row][col] == num) {
                return true;
            }
        }
        return false;
    }

    // 检查在当前列是否已经使用了指定数字
    private boolean usedInColumn(int col, int num) { //遍历实现
        for (int[] ints : board) {
            if (ints[col] == num) {
                return true;
            }
        }
        return false;
    }

    // 检查在当前子网格是否已经使用了指定数字
    private boolean usedInSubgrid(int startRow, int startCol, int num) { //遍历实现
        for (int row = 0; row < 3; row++) {
            for (int col = 0; col < 3; col++) {
                if (board[row + startRow][col + startCol] == num) {
                    return true;
                }
            }
        }
        return false;
    }

    // 获取解的数量
    public int getCount() {
        return count;
    }
}
